﻿using System;
using System.Collections.Generic;

namespace Project1
{
	/// <summary>
	/// Represents a state in a search problem state space.
	/// </summary>
    public class State : IComparable<State>
    {
        private State parentState;
        private int pathCost;
        private int pathLength = 0;
        private int heuristicCost;
        private Object key;

        /// <summary>
        /// This is a unique identifier for this particular state. In case the state space 
        /// represents a two-dimensional grid then this would be the co-ordinates of a cell.
        /// </summary>
        public Object Key
        {
            get { return key; }
        }

		/// <summary>
		/// Gets the parent state (the predecessor).
		/// </summary>
		/// <value>
		/// The parent state.
		/// </value>
		/// <remarks>This property can be used to traverse the path backwards to the initial state.</remarks>
        public State ParentState
        {
            get { return parentState; }
        }

		/// <summary>
		/// Gets the path cost to this state (g(n)).
		/// </summary>
        public int PathCost
        {
            get
            {
                return this.pathCost;
            }
        }

		/// <summary>
		/// Gets the length of the path to this state.
		/// </summary>
		/// <value>
		/// The length of the path.
		/// </value>
        public int PathLength
        {
            get
            {
                return this.pathLength;
            }
        }

		/// <summary>
		/// Gets or sets the heuristic cost (h(n)).
		/// </summary>
		/// <value>
		/// The heuristic cost.
		/// </value>
        public int HeuristicCost { get { return heuristicCost; } set { heuristicCost = value; } }

		/// <summary>
		/// Gets the combined path and heuristic cost (f(n) = g(n) + h(n)).
		/// </summary>
		public int CombinedCost
		{
			get
			{
				return this.PathCost + this.HeuristicCost;
			}
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="State"/> class.
		/// </summary>
		/// <param name="key">The state key.</param>
		/// <param name="edgeCost">The edge cost from the parent state to this state.</param>
        public State(Object key, int edgeCost)
            : this(key, edgeCost, null)
        {

        }

		/// <summary>
		/// Initializes a new instance of the <see cref="State"/> class.
		/// </summary>
		/// <param name="key">The state key.</param>
		/// <param name="edgeCost">The edge cost from the parent state to this state.</param>
		/// <param name="parentState">The parent state.</param>
        public State(Object key, int edgeCost, State parentState)
        {
            this.key = key;
            this.parentState = parentState;
            this.pathCost = edgeCost;
            if (this.parentState != null)
            {
                this.pathCost += this.parentState.PathCost;
                this.pathLength = this.parentState.PathLength + 1;
            }
        }

		/// <summary>
		/// Determines whether the specified <see cref="System.Object"/> is equal to this instance.
		/// </summary>
		/// <param name="obj">The <see cref="System.Object"/> to compare with this instance.</param>
		/// <returns>
		///   <c>true</c> if the specified <see cref="System.Object"/> is equal to this instance; otherwise, <c>false</c>.
		/// </returns>
		/// <exception cref="T:System.NullReferenceException">
		/// The <paramref name="obj"/> parameter is null.
		///   </exception>
        public override bool Equals(object obj)
        {
			//
			// Use the key for comparison. Keep in mind that the states may not be exactly the same, 
			// i.e. they may have been reached by different paths.
			//
            return this.key.Equals(((State)obj).key);
        }

		/// <summary>
		/// Gets the path string.
		/// </summary>
        public string GetPathString()
        {
			//
			// Travel the path backwards and collect the keys of each state
			//
            List<State> path = new List<State>();
            State current = this;
            do
            {
                path.Add(current);
                current = current.ParentState;
            } while (current != null);
			//
			// Now iterate through the key collection in reverse order to get the forward path.
			//
            string result = "";
            for (int index = path.Count - 1; index >= 0; index--)
            {
                result += path[index].Key.ToString();
                if (index > 0)
                {
                    result += " -> ";
                }
            }
			//
			// Return the path of state keys
			//
            return result;
        }

		/// <summary>
		/// Gets the keys of the states on the path from the current state to the initial state.
		/// </summary>
		/// <returns>An array of keys</returns>
        public Object[] GetKeys()
        {
            List<Object> keys = new List<Object>();
            State current = this;
            do
            {
                keys.Add(current.Key);
                current = current.ParentState;
            } while (current != null);

            return keys.ToArray();
        }

        #region IComparable<State> Members
		/// <summary>
		/// Compares two states using the CombinedCost property.
		/// </summary>
		/// <param name="other">The other state.</param>
		/// <returns>
		/// A negative number of the current state is smaller than the other state, 
		/// 0 if they are equal, otherwise a  positive number.
		/// </returns>
        int IComparable<State>.CompareTo(State other)
        {
            return this.CombinedCost.CompareTo(other.CombinedCost);
        }
        #endregion

		/// <summary>
		/// Checks whether the state path contains the supplied <paramref name="State"/>.
		/// </summary>
		/// <param name="state">The state to look for.</param>
		/// <returns>
		/// <c>true</c> if the state is found on the path from the current state to the initial state, 
		/// otherwise <c>false</c>.
		/// </returns>
        internal bool PathContains(State state)
        {
			//
			// First check if the current state has the same key (and is therefore considered to be equal).
			//
			bool result;
            if (state.Key.Equals(this.Key))
            {
                result = true;
            }
			//
			// Then use recursion to see if we find a state with the same key higher up on the path.
			//
			else if (this.ParentState != null)
			{
				result = this.ParentState.PathContains(state);
			}
			else
			{
				//
				// This is the terminating case, we've reached the initial state without finding the state
				// we were looking for.
				//
				result = false;
			}
            return result;
        }
    }
}
